package cc.ccoke.algorithms.primary.chapter02;

import cc.ccoke.algorithms.util.ArrayUtils;

import java.util.Scanner;


/**
 * 荷兰国旗问题
 * 给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。
 * @author ccoke
 */
public class HollandFlag {
    public static void sort(int[] arr, int num) {
        int p = -1;
        int q = arr.length;
        int index = 0;
        while (index < q) {
            if (arr[index] < num) {
                ArrayUtils.swap(arr, ++p, index ++);
            } else if (arr[index] > num) {
                ArrayUtils.swap(arr, --q, index);
            } else {
                index ++;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateByInt(10, 20);
        System.out.println("--- before ---");
        ArrayUtils.print(arr);
        System.out.println("--- after ---");
        Scanner sc = new Scanner(System.in);
        System.out.print("input number:");
        int num = sc.nextInt();
        sort(arr, num);
        ArrayUtils.print(arr);
    }

}
